package a14_Sort;

/**
 * @Author quan
 * @Description 堆排序：自己没有写，复制粘贴的
 * @Date 2023/4/30 18:12
 */
public class StackSort {
    //原地堆排序
    public static void heapSort(int[] arr){
        //1、先将任意数组堆化，使其变为一个最大堆
        //从最后一个非叶子节点不断向前看，进行下沉操作
        for (int i = (arr.length-1-1) / 2; i > 0 ; i--) {
            siftDown(arr,i,arr.length);
        }
        //2、不断地将当前无序数组的最大值(堆顶)和最后一个元素交换
        for (int i = arr.length - 1; i > 0 ; i--) {
            //将堆顶元素和i交换，i是无序数组的最后一个元素
            swap(arr,0,i);
            //交换完之后进行元素的下沉操作
            siftDown(arr,0,i);
        }
    }
    //在数组arr上进行元素下沉操作
    private static void siftDown(int[] arr, int k, int size) {
        //当前节点的左孩子节点
        int j = 2 * k + 1;
        while (j < size){
            //在左子树存在的条件下
            //如果右子树也存在，且右子树的值大于左子树
            if(j + 1 < size && arr[j+1] > arr[j]){
                //将j更新为最大值所在的索引
                j = j + 1;
            }
            //此时j保存了左右子树最大值索引
            if(arr[k] < arr[j]){
                //如果此时根的值小于左右子树的最大值
                //先交换元素的值
                swap(arr,k,j);
                //再更新k的值
                k = j;
                j = 2 * k + 1;
            }else{
                //此时根的值大于左右子树的最大值，不用交换
                break;
            }
        }
    }
    //将两个节点的值交换
    private static void swap(int[] arr,int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
